<head>
    <meta charset="UTF-8">
<title>算法提高 Flight Planning</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<div>你的任务是写一个程序来完成飞机的飞行计划. 每一次飞行都可以被分为一系列的航段。你的程序必须对每一航段选出最佳的飞行高度，以最小化航程中需要消耗的燃料。</div>
<div>飞机的空速是给定的，我们将用VCRUISE来描述。以及一个效果最佳的飞行高度AOPT（单位为英尺）。当飞机以海拔为AOPT的高度飞行时，每小时将消耗燃料GPHOPT加仑。如果飞机不在AOPT高度飞行，每低于或高于AOPT 1000英尺，每小时消耗的燃料就会额外增加GPHEXTRA加仑。飞机的起飞前的高度、降落后的高度均为0. 飞机的飞行高度每提升1000英尺，燃料就会消耗CLIMBCOST加仑（飞行高度下降是不需要消耗燃料的），为了简化问题，我们认为飞机的飞行高度变化是瞬间完成的。以上的所有参数，在下表中给出：</div>
<div>&nbsp;</div>
<div>VCRUSITE &nbsp;400 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;海里 / 小时</div>
<div>AOPT &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 30,000 &nbsp; &nbsp; &nbsp; 英尺</div>
<div>GPHOPT &nbsp; &nbsp; 2000 &nbsp; &nbsp; &nbsp; &nbsp; 加仑 / 小时</div>
<div>GPHEXTRA &nbsp;10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 加仑 / 1000英尺</div>
<div>CLIMBCOST 50 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 加仑 / 1000英尺&nbsp;</div>
<div>&nbsp;</div>
<div>每次飞行前，你都会得知每一航段的长度，以及每一航段的风速。风速并不是确定的，具体地说，它由飞机在该航段的飞行高度决定，并且是一个关于飞行高度的线性函数。例如，如果飞机的空速是400海里/小时，而风速是-50海里/小时时，飞机的实际对地速度就是350海里/小时。</div>
<div>由于某些特殊的规定，飞机在每一航段的飞行高度必须在20,000英尺~40,000英尺之间，且必须是1000英尺的整数倍。你的程序需要在最小化消耗燃料的前提下，输出每一航段的飞行高度，以及消耗的最少燃料。</div>
<p>【输入格式】</p>
<p>第一行一个整数N，表示有N组数据。</p>
<p>对于每组数据，第一行包含一个整数K（K&le;100），描述航段数量。</p>
<p>接下来K行，每行3个整数A、B、C，分别描述该航段的长度（单位为海里）、在20,000英尺时的风速（单位为海里/小时)、在40,000英尺时的风速。</p>
<p>【输出格式】<br />
对于每组数据，输出一行，共k+1个整数。前k个整数分别描述每个航段的飞行高度(单位为1000英尺），最后一个整数描述消耗的最少燃料，由于答案有可能是实数，请对答案取上整后输出。如果有多种方案满足要求，请选择字典序最小的方案（例如当 K = 2 时，有2种方案(30, 40) 和 (20, 30)，则输出(20, 30))。具体格式见样例输出。<br />
【样例输入】</p>
<p>2</p>
<p>2</p>
<p>1500 -50 50</p>
<p>1000 0 0</p>
<p>3</p>
<p>1000 50 0</p>
<p>2000 0 20</p>
<p>1800 50 100</p>
<p>【样例输出】</p>
<p>Flight 1: 35 30 13986</p>
<p>Flight 2: 20 30 30 23502</p>
<p>【数据规模和约定】<br />
K&le;100，A&le;100,000，|B|、|C|&le;100</p>
<p>&nbsp;</p>
<p>【特殊说明】</p>
<p>请注意-O2下的精度问题</p>